package com.leetcode.algorithm.y22.m08.w3;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 538. 把二叉搜索树转换为累加树
 * 
 * https://leetcode.cn/problems/convert-bst-to-greater-tree/
 * 
 * @author jie.deng
 *
 */
class Question0538Solution01 {

	public TreeNode convertBST(TreeNode root) {
		convertBST(root, new int[] { 0 });
		return root;
	}

	private void convertBST(TreeNode root, int[] sumArr) {
		if (root == null) {
			return;
		}
		convertBST(root.right, sumArr);
		sumArr[0] += root.val;
		root.val = sumArr[0];
		convertBST(root.left, sumArr);
	}

}